﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    public class Node
    {
        public object Data { get; set; }
        public Node CLeft { get; set; }
        public Node CRight { get; set; }
    }
    public class BiTree
    {
        public Node Root { get; set; } = new Node();
        public string Str { get; set; }
        int index = 0;

        public Node CreateBiTreeByString(Node bt)
        {
            char ch = getChar();
            if (ch == char.MinValue) return null;

            if (ch == '.')
            {
                return null;
            }
            else
            {
                bt.Data = ch;
                bt.CLeft = new Node();
                bt.CRight = new Node();
                bt.CLeft = CreateBiTreeByString(bt.CLeft);
                bt.CRight = CreateBiTreeByString(bt.CRight);
            }
            return bt;
        }
        char getChar()
        {
            if (Str.Length > index)
            {
                return Str[index++];
            }
            return char.MinValue;
        }

        public void PreOrder2(Node node)
        {
            if (node == null)
                return;

            Stack<Node> stack = new Stack<Node>();
            stack.Push(node);
            while (stack.Count != 0)
            {
                var tmp = stack.Pop();
                if (tmp != null)
                {
                    Console.Write(tmp.Data);
                    if (tmp.CRight != null)
                        stack.Push(tmp.CRight);
                    if (tmp.CLeft != null)
                        stack.Push(tmp.CLeft);
                }
            }
        }

        public void InOrder2(Node node)
        {
            if (node == null)
                return;

            Queue<Node> stack = new Queue<Node>();
            stack.Enqueue(node);
            while (stack.Count != 0)
            {
                var tmp = stack.Dequeue();
                if (tmp != null)
                {
                    Console.Write(tmp.Data);

                    if (tmp.CRight != null)
                        stack.Enqueue(tmp.CRight);
                    if (tmp.CLeft != null)
                        stack.Enqueue(tmp.CLeft);
                }
            }
        }
        public void PreOrder(Node node)
        {
            if (node != null)
            {
                Console.Write(node.Data);
                PreOrder(node.CLeft);
                PreOrder(node.CRight);
            }
        }

        public void InOrder(Node node)
        {
            if (node != null)
            {
                InOrder(node.CLeft);
                Console.Write(node.Data);
                InOrder(node.CRight);
            }
        }
        public void PostOrder(Node node)
        {
            if (node != null)
            {
                PostOrder(node.CLeft);
                PostOrder(node.CRight);
                Console.Write(node.Data);
            }
        }


        public int GetNodeNums(Node node)
        {
            int count = 0;
            if (node != null)
            {
                count++;

                count += GetNodeNums(node.CLeft);
                count += GetNodeNums(node.CRight);
            }
            return count;
        }

        public int GetYeziNums(Node node)
        {
            int count = 0;
            if (node != null)
            {
                if (node.CLeft == null
                && node.CRight == null)
                    count++;
                count += GetYeziNums(node.CLeft);
                count += GetYeziNums(node.CRight);
            }
            return count;
        }

        /// <summary>
        /// 计算深度
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public int GetDepth(Node node)
        {
            //先序遍历        
            if (node == null)
                return 0;
            else
            {
                int leftH = GetDepth(node.CLeft);
                int rightH = GetDepth(node.CRight);
                return Math.Max(leftH, rightH) + 1;
            }
        }

        /// <summary>
        /// 统计每一层节点的数量
        /// </summary>
        /// <param name="node"></param>
        /// <param name="level"></param>
        /// <returns></returns>
        public int GetLevelsNums(Node node, int level)
        {
            //先序遍历        
            int count = 0;
            if (node == null || level < 1)
                return 0;
            if (level == 1)
            {
                count++;
            }
            count += GetLevelsNums(node.CLeft, level - 1);
            count += GetLevelsNums(node.CRight, level - 1);
            return count;
        }

        /// <summary>
        /// 根据先序和中序
        /// </summary>
        /// <param name="preOrder"></param>
        /// <param name="inOrder"></param>
        /// <returns></returns>
        public Node ReturnPostOrder(string preOrder, string inOrder)
        {
            //怎么把人脑思考的过程转化成机器,我觉得机器应该不可能超过人脑            

            if (string.IsNullOrEmpty(preOrder))
                return null;

            char start = preOrder[0];
            Node root = new Node() { Data = start };

            int leftIndex = inOrder.IndexOf(start);
            if (leftIndex < 0)
            {
                return null;
            }
            string inleftStr = inOrder.Substring(0, leftIndex);
            string inrightStr = inOrder.Substring(leftIndex + 1);
            string preleftStr = new string(preOrder.ToArray().
                Where(s => inleftStr.Contains(s)).ToArray());
            string prerightStr = new string(preOrder.ToArray().
                Where(s => inrightStr.Contains(s)).ToArray());


            root.CLeft = ReturnPostOrder(preOrder: preleftStr, inOrder: inleftStr);
            root.CRight = ReturnPostOrder(preOrder: prerightStr, inOrder: inrightStr);
            return root;
        }

        /// <summary>
        /// 交换左右树
        /// </summary>
        public void ExchangeChildren(Node node)
        {
            if (node == null)
                return;

            Node tmp = node.CLeft;
            node.CLeft = node.CRight;
            node.CRight = tmp;

            ExchangeChildren(node.CLeft);
            ExchangeChildren(node.CRight);
        }
    }
}
